package pro.softzhang.algo.abc;

/**
 * 排序方法
 */
public class Sort {
    public static void main(String[] args) {

    }

    /**
     * 快速排序
     */
    static class QuickSort {

        public static void main(String[] args) {
            int[] arr = {9,8,7,5,2,2,1,32,9,3,0,34338,7,65};
            printArray("排序前：", arr);
            quickSort(arr,0,arr.length-1);
            printArray("排序后：", arr);
        }

        /**
           * 核心思想：1.指针初始，标准设定+右方开始，大小分开+指针重合，标准中间；2.分而治之
         */
        private static void quickSort(int[] arr,int left,int right){//最左角标与最右角标
            //0.是否排序，如果等于或大于没有就不能执行。
            if(left < right){
                //1.设定标准
                int standard = arr[left];
                //2.大小分开
                //2.1.指针初始，明确标准
                int leftPointer = left; 
                int rightPointer = right;
                //2.2.循环开始，大小分开。
                while(leftPointer < rightPointer){//左边有坑看右边，右边有坑看左边。
                    //2.2.1.右方找小，放到左方（左方开始会丢失数据），因为左方出空位子。
                    // 永远记住是与标准比，进而完成分组。
                    while(leftPointer < rightPointer && arr[rightPointer] >= standard){
                        rightPointer--;//右边出来一个坑，需要进行处理。
                    }
                    if(leftPointer < rightPointer){//只要没有相等或小于leftPointer，进行交换。 
                        arr[leftPointer] = arr[rightPointer];
                        leftPointer++;
                    }
                    //2.2.2.左方找大，放到右方。因为左方出现空位子。
                    while(leftPointer < rightPointer && arr[leftPointer] <= standard){//到左边，小于rightPointer的。
                        leftPointer++;
                    }
                    // //要么第1个错，要么两个全错，“短路”；为防止是leftPointer > rightPointer。
                    if(leftPointer < rightPointer){
                        arr[rightPointer] = arr[leftPointer];
                        rightPointer--;
                    }
                }
                //2.3.指针重合，标准中间，剩下的空就是standard留下的。
                arr[leftPointer] = standard;
                //3.分而治之，空着中间。快速的关键所有，相当于多条线程处理同一问题，当然快。
                quickSort(arr, left, leftPointer-1);//撇过中间，加1与减1
                quickSort(arr, rightPointer+1, right);
            }
        }

        private static void printArray(String desc,int[] arr){
            System.out.println(desc);
            for(int item:arr)
            System.out.print(item+" ");
            System.out.println();
        }
    }
}
